package main

// 946. 验证栈序列
// 给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，
// 只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

// 翻译有问题，意思是：已知pushed序列，是否可以控制push和pop操作，得到popped序列
// 如pushed=[1,2,3,4,5] 可能得到popped[4,5,3,2,1]

// 模拟栈

func validateStackSequences(pushed []int, popped []int) bool {
	if len(popped) != len(pushed) {
		return false
	}
	if len(pushed) == 0 {
		return true
	}
	stack := []int{pushed[0]}
	for i := 1; i < len(pushed); i++ {
		// 判断栈顶
		for len(stack) > 0 && stack[len(stack)-1] == popped[0] {
			// 弹出栈顶
			stack = stack[:len(stack)-1]
			popped = popped[1:]
		}
		stack = append(stack, pushed[i])
	}
	// 栈 只能弹出
	for len(stack) > 0 {
		top := stack[len(stack)-1]
		if top != popped[0] {
			return false
		}
		stack = stack[:len(stack)-1]
		popped = popped[1:]
	}
	return true
}

func main() {
	pushed := []int{1, 2, 0}
	poped := []int{2, 1, 0}
	res := validateStackSequences(pushed, poped)
	println(res)
}
